package pl.wroc.uni.ii.evolution.engine.operators.spacespecific.binaryvector.ecga;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

import pl.wroc.uni.ii.evolution.engine.EvPopulation;
import pl.wroc.uni.ii.evolution.engine.individuals.EvBinaryVectorIndividual;
import pl.wroc.uni.ii.evolution.engine.prototype.EvOperator;
import pl.wroc.uni.ii.evolution.solutionspaces.EvBinaryVectorSpace;


/**
 * Computes best ECGAStructure for given population using greedySearch.
 * 
 * @author Marcin Golebiowski
 */
public class EvStructureDiscover implements EvOperator<EvBinaryVectorIndividual> {
  private EvBinaryVectorSpace space;
  private EvECGAStructure struct;
  private EvPopulation<EvBinaryVectorIndividual> population;
  private boolean use_previous_structure;
  
  final double log2 = Math.log(2);
  
  /**
   * constructor
   * @param space binary strings solution space
   * @param use_previous_structure 
   */
  public EvStructureDiscover(EvBinaryVectorSpace space, boolean use_previous_structure) {
    this.space = space;
    this.use_previous_structure = use_previous_structure;
  }
  
  
  /* (non-Javadoc)
   * @see pl.wroc.uni.ii.evolution.engine.prototype.EvolutionaryOperator#apply(pl.wroc.uni.ii.evolution.engine.Population)
   */
  public EvPopulation<EvBinaryVectorIndividual> apply(EvPopulation<EvBinaryVectorIndividual> population) {
    this.population = population;
    greedySearch();
    System.out.println(struct);
    return population;
  }

  
  private void greedySearch() {
    
    // creating buffor of fast Integer objects
    int pop_size = population.size();
    EvECGAFastHashMap map = new EvECGAFastHashMap(pop_size);

    
    /** init structure */
    if (struct == null || !use_previous_structure) {
      struct = new EvECGAStructure();

      for (int i = 0; i < space.getDimension(); i++) {
        EvBlock some = new EvBlock();
        some.put(i);

        some.setRating(getCombinedComplexity(some, population, map));
        struct.addBlock(some);
      }

    }
	  /** init cache */
    EvCache merged_blocks_cache = new EvCache();
    
    /** iterate over all possible two elements subset */ 
    EvSubsetTwoIterator iterator = new EvSubsetTwoIterator(struct.getSetCount());
    while (iterator.hasNext()) {
      EvPair selected = iterator.next();
      EvBlock first = struct.getBlock(selected.x);
      EvBlock second = struct.getBlock(selected.y);
      EvBlock result = new EvBlock();
      result.merge(first);
      result.merge(second);
      
      /** compute rating for result */
      result.setRating(getCombinedComplexity(result, population, map));
     
      EvMergedBlock merged = new EvMergedBlock(first, second, result);
      merged_blocks_cache.put(merged);
    }
    
	  /** do search */
    while (merged_blocks_cache.getCacheSize() > 0) {
      
      /** search cache */
      EvMergedBlock best_block_to_merge = merged_blocks_cache.getBestMerged();

      if ((best_block_to_merge != null) && (best_block_to_merge.getProfit() > 0)) {
   
        
        /** Structure update */
        
    	  /** add to structure result of best merge (a + b) */
    	  struct.addBlock(best_block_to_merge.getResult());
    	  /** remove from structure  a and b */
        struct.remove(best_block_to_merge.getFirst(), best_block_to_merge.getSecond());
     
        
        /** Update cache */
     
        /** remove from cache all invalid entries */
        merged_blocks_cache.remove(best_block_to_merge.getFirst(), best_block_to_merge.getSecond());
        
        /** add to cache all combination of best_block_to_merge and all other blocks */
        for (int i = 0; i < struct.getSetCount(); i++) {
          if (struct.getBlock(i) != best_block_to_merge.getResult()) {
            
            EvBlock new_block = new EvBlock();
            new_block.merge(best_block_to_merge.getResult());
            new_block.merge(struct.getBlock(i));
            new_block.setRating(getCombinedComplexity(new_block, population, map));
            
            merged_blocks_cache.put(new EvMergedBlock(best_block_to_merge.getResult(),
                struct.getBlock(i), new_block));
            
          }
        }
      } else {
        break;
      }
    }
    
  }
  
  /**
   * Computes combined complexity for given structure
   * 
   * @param struct
   * @param population
   * @return CombinedComplexity 
   */
  public double getCombinedComplexity(EvBlock block, 
      EvPopulation<EvBinaryVectorIndividual> population, EvECGAFastHashMap map) {
    
    double cpc = getCompressedPopulationComplexity(block, population, map);
    double mc = getModelComplexity(block, population);
    
    if (Double.MAX_VALUE - mc < cpc) {
      return Double.MAX_VALUE;
    } else {
      return mc + cpc;
    }
  }
  
  /**
   * Computes model complexity for given block
   * 
   * @param struct
   * @param population
   * @return ModelComplexity
   */
  public double getModelComplexity(EvBlock block, 
      EvPopulation<EvBinaryVectorIndividual> population) {
    
    double mc = 0.0;
    int pop_size = population.size();

    if (block.getSize() > 63) {
      return Double.MAX_VALUE;
    }
    
    double val = Math.pow(2, block.getSize());
    if (Double.MAX_VALUE - val < mc) {
      return Double.MAX_VALUE;
    }
    mc += val;

    double logp = Math.log(pop_size) / Math.log(2);
    if (Double.MAX_VALUE/mc < logp ) {
      return Double.MAX_VALUE;
    }
    return mc * logp;
  }

  /**
   * Computes compressed population complexity for given block
   * 
   * @param struct
   * @param population
   * @return CompressedPopulationComplexity
   */
  public double getCompressedPopulationComplexity(EvBlock block,
      EvPopulation<EvBinaryVectorIndividual> population, EvECGAFastHashMap map) {
    // sets the Double map object
    // this helps to avoid time consuming boxing of double values
    // ########## NOTE!!! ############
    // this function is called milion times and it's performance must be
    // as good as possible. Don't put any Sugar here or beautify any code or
    // put anything here without performance testing.
    // Don't worry with the code style - it's bad but because it have to run fast
    
    double CPC = 0;

    int i=0;
    int population_size = population.size();
    
    map.clear();
    
    
    //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
    // transforming ArrayList<Integer> to int[]
    int block_values_size = block.values.size();
    
    int[] block_tab = new int[block_values_size];
    for (i=0; i < block_values_size; i++) {
      block_tab[i] = block.values.get(i);
    }
    // end of  transforming ArrayList<Integer> to int[]
    //@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ 
    
    boolean[] result = new boolean[block_values_size];    
    boolean[] genes;

    // MAIN LOOP
    // this whole thing counts number of individuals with the same subvector
    int k;
    for (i=0; i < population_size; i++) {
      
      // @@@@ function boolean[] subvector I PUT IT DIRECTLY HERE FOR BETTER PERFORANCE@@@@
      genes = population.get(i).vector;

      for (k = 0; k < block_values_size; k++) {
         result[k] = genes[block_tab[k]];
      } 
      //    @@@@ end of function boolean[] subvector @@@@
      
      //    hashing subvector so we can put it in hash table    
      
      map.put(Arrays.hashCode(result));
      
      
    }

    double population_size_double = (double)population_size;
    
    int[] counts = map.getCount();
    
    for (i=0; i < counts.length; i++) {
      double p = (double)counts[i] / population_size_double;
      CPC -= (Math.log(p) / log2) * p;      
    }

    return CPC * population_size_double;
  }  
  
  
  // returns boolean subvector of vector genes
  /*
  private boolean[] subvector(boolean[] genes, int[] elements) {
    
    int j = 0;
    int elements_size = elements.length;
    boolean[] result = new boolean[elements_size];
    for (int i = 0; i < elements_size; i++) {
       result[j] = genes[elements[i]];
       j++;
    }
    return result;
  }*/


  public  EvECGAStructure getStruct() {
    return this.struct;
  }
  
  
}
